// 1042113.cpp : Defines the entry point for the console application.
//
//--Khai bao thu vien
//------------------------------
#include "stdafx.h"
//------------------------------
//--Khai bao thu vien doc file
#include "fstream"
#include "iostream"
using namespace std;
//------------------------------

#define MAX 100
class Graph
{
public:
	//--Ham void
	void GetData(const char *filename);
	void OutScreen(int Number);
	void Count(int Number);
	void Sort();
	void WriteData(const char *filename);
	//--Ham int
	int FindConnected();
	int TestGraph();
protected:
	//--So dinh cua do thi, danh so tu 0
	int nVertex;
	//--Nhan cua cac dinh
	//--Thiet ke labels gom co : 
	//--Dong 1 : ten dinh
	//--Dong 2 : thanh phan lien thong
	//--Dong 3 : so dinh cua thanh phan lien thong
	int labels[3][MAX];
	//--Ma tran ke
	int Ma_tran_ke[MAX][MAX];
	void Visit(int i, int label);
	void Swap(int &a, int &b);
private:
};
//------------------------------
//--Doc du lieu file
void Graph::GetData(const char *filename)
{
	//--Nhap du lieu tu tap tin van ban
	ifstream fin;
	fin.open(filename);
	fin >> nVertex;
	for (int i = 0; i < nVertex; ++i)
	{
		for (int j = 0;j < nVertex; ++j)
		{
			fin >> Ma_tran_ke[i][j];
		}
	}
}
//------------------------------
//--Gan nhan cho mot thanh phan lien thong
void Graph::Visit(int i, int label)
{
	labels[1][i] = label;
	for (int j = 0; j < nVertex; j++)
	{
		if((labels[1][j] == 0)&&(Ma_tran_ke[i][j]||Ma_tran_ke[j][i]))
		{
			Visit(j,label);
		}
	}
}
//------------------------------
//--Gan nhan cho tat ca thanh phan lien thong
int Graph::FindConnected()
{
	int i, label;
	for (i = 0; i < nVertex; i++)
	{
		//--Dong 1 : ten dinh
		labels[0][i] = i;
		//--Dong 2 : thanh phan lien thong
		labels[1][i] = 0;
	}
	label = 0;
	for (i = 0; i < nVertex; i++)
	{
		if(labels[1][i] == 0)
		{
			label ++ ;
			Visit(i,label);
		}
	}
	return label;
}
//------------------------------
//--Dem so dinh co cung thanh phan lien thong
void Graph::Count(int Number)
{
	for (int i=0; i <= Number ; i++)
	{
		int count = 0;
		for (int j = 0; j < nVertex; j++)
		{
			if (labels[1][j] == i)
			{
				count ++;
			}
		}
		for (int j = 0; j < nVertex; j++)
		{
			if (labels[1][j] == i)
			{
				labels[2][j] = count;
			}
		}
	}
}
//------------------------------
//--Ham hoan vi
void Graph::Swap(int &a, int &b)
{
	int c;
	c = a;
	a = b;
	b = c;
}
//------------------------------
//--Sap xep cac thanh phan lien thong
void Graph::Sort()
{
	//--Tao mot ma tran ao chua cac phan tu duoc sap xep
	int VirtualMatrix[3][MAX];
	int k=0;
	for (int i=1; i < nVertex; i++)
	{
		for (int j=0; j < nVertex; j++)
		{
			if(labels[1][j]==i)
			{
				VirtualMatrix[0][k]=labels[0][j];
				VirtualMatrix[1][k]=labels[1][j];
				VirtualMatrix[2][k]=labels[2][j];
				k++;
			}
		}
	}
	k=0;
	for (int i=1; i < nVertex; i++)
	{
		for (int j=0; j < nVertex; j++)
		{
			if(VirtualMatrix[2][j]==i)
			{
				labels[0][k]=VirtualMatrix[0][j];
				labels[1][k]=VirtualMatrix[1][j];
				labels[2][k]=VirtualMatrix[2][j];
				k++;
			}
		}
	}
}
//------------------------------
//--Kiem tra do thi
int Graph::TestGraph()
{
	//--Kiem tra do thi co huong hay khong
	for (int i=0;i<nVertex;i++)
	{
		for (int j=0 ; j< nVertex;j++)
		{
			if (Ma_tran_ke[i][j]!=Ma_tran_ke[j][i])
			{
				return 0;
			}
		}
	}
	//--Kiem tra ma tran co hop le hay khong
	for (int i=0;i<nVertex;i++)
	{
		if (Ma_tran_ke[i][i]!=0)
		{
			return 0;
		}
	}
	return 1;
}
//--Xuat ra man hinh
void Graph::OutScreen(int Number)
{	
	printf(" %d\n",Number);
	for(int j=0;j<nVertex;j++)
	{
		if(labels[1][j]!=labels[1][0])
		{
			if(labels[1][j-1]!=labels[1][j])
			{
				printf("\n");
			}
		}
		printf(" %d ",labels[0][j]);
	}
	printf("\n");
}
//------------------------------
//--Ghi file
void Graph::WriteData(const char *filename)
{
	//--Ghi file
	ofstream fin;
	fin.open(filename);
	int i = FindConnected();
	Count(i);
	Sort();
	fin << " " << i;
	fin << "\n";
	for(int j=0;j<nVertex;j++)
	{
		if(labels[1][j]!=labels[1][0])
		{
			if(labels[1][j-1]!=labels[1][j])
			{
				fin << "\n";
			}
		}
		fin << " " << (labels[0][j]) << " ";
	}
	fin.close();
}
//------------------------------
void main (int argc, char *argv[])
{
	if(argc == 3)
	{
		Graph G;
		G.GetData(argv[1]);
		int kq = G.TestGraph();
		if(kq == 1)
		{
			int i = G.FindConnected();
			G.Count(i);
			G.Sort();
			G.OutScreen(i);
			G.WriteData(argv[2]);
		}
		else
		{
			printf("Ma tran nhap sai \n");
		}
	}
	else
		printf("Tham so dong lenh nhap sai\n");
}
